package leetcode.pre100;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
 * <p>
 * 有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
 * <p>
 *  
 * <p>
 * 示例:
 * <p>
 * 输入: "25525511135"
 * 输出: ["255.255.11.135", "255.255.111.35"]
 * <p>
 *
 * @since 2020/6/10 0010 下午 9:11
 */
public class Code93_RestoreIP_复原IP {
    public static void main(String[] args) {
        String s = "010010";
        System.out.println(restoreIpAddresses(s));
    }

    public static List<String> restoreIpAddresses(String s) {
        List<String> res = new LinkedList<>();
        if (s == null || s.length() <= 3) return res;
        //方式1：回溯，当前ip可以回溯1位或2位或3位
        process(s, 0, new Stack<String>(), res);
        return res;
    }

    private static void process(String s, int i, Stack<String> stack, List<String> res) {
        if (stack.size() == 4) {
            if (i == s.length()) {
                StringBuffer sb = new StringBuffer();
                for (int j = 0; j < stack.size() - 1; j++) {
                    sb.append(stack.get(j)).append(".");
                }
                sb.append(stack.get(stack.size()-1));
                res.add(sb.toString());
            }
            return;
        }
        if (i >= s.length()) return;
        //可以1位,2位，3位
        for (int j = 1; j <= 3; j++) {
            if (i + j <= s.length()) {
                String substring = s.substring(i, i + j);
                //0.1.2.3    合法
                //02.01.02.03 不合法，该位置除非是0，不能以0开头
                if(substring.length() >= 2 && substring.charAt(0) == '0') continue;
                if (Integer.parseInt(substring) <= 255) {
                    stack.push(substring);
                    process(s, i + j, stack, res);
                    stack.pop();
                }
            }
        }
    }
}
